#include<cstdio>
#include<cstring>
const int maxn=1000010;
int next[maxn],m;
char p[maxn];
void work()
{
	m=strlen(p+1);
	next[1]=0;
	int k=0;
	for(int q=2;q<=m;q++)
	{
		while(k>0&&p[k+1]!=p[q])k=next[k];
		if(p[k+1]==p[q])k++;
		next[q]=k;
	}
}
int main()
{
	freopen("test.in","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--)
	{
	//	memset(p,0,sizeof(p));
		memset(next,0,sizeof(next));
		scanf("%s",p+1);
		work();
		int cyc=m-next[m];
		int ans;
		if(m>cyc&&m%cyc==0)ans=0;
		else  ans=cyc-m%cyc;
		printf("%d\n",ans);
	}
	return 0;
}

